package alogrithm;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/9/10 22:09
 */
public class ChalkReplacer {
    public static void main(String[] args) {
        int[] chalk = new int[]{5, 1, 5};
        int k = 22;
        final int i = chalkReplacer(chalk, k);
        System.out.println(i);
    }

    public static int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        if (chalk[0] > k) {
            return 0;
        }
        for (int i = 1; i < n; ++i) {
            chalk[i] += chalk[i - 1];
            if (chalk[i] > k) {
                return i;
            }
        }
        k = k % chalk[n - 1];
        return binarySearch(chalk, k);
    }

    private static int binarySearch(int[] chalk, int k) {

        int low = 0;
        int high = chalk.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (chalk[mid] > k) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}
